This invention relates to automatic reclamation of allocated, but unused memory, or garbage, in a computer system that uses a generational garbage collector and, particularly, to techniques for reducing object copying during garbage collection cycles. Memory reclamation may be carried out by a special-purpose garbage collection algorithm that locates and reclaims memory that is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms which reclaim memory allocated to objects by object-oriented programs, including reference counting, mark-sweep, mark-compact and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms for Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
However, many of the aforementioned garbage collection techniques often lead to long and unpredictable delays because normal processing must be suspended during the garbage collection process and these collectors at least occasionally scan the entire heap. The garbage collection process is performed by collection threads that perform collection work when all other threads are stopped. Therefore, these techniques are generally not suitable in situations, such as real-time or interactive systems, where non-disruptive behavior is of greatest importance.
Conventional generational collection techniques alleviate these delays somewhat by concentrating collection efforts on a small memory area, called the “young” generation, in which most of the object allocation activity occurs. Generational garbage collection has been a very successful strategy. It relies on an empirical observation that has been found to be true of many programs: that recently allocated objects are more likely to become unreachable than older objects that have already survived several garbage collection cycles. Dividing up a garbage-collected heap into a young and an old generation allows a copying garbage collection technique to be used for collection of the young generation, where survival rates are fairly low, and a garbage collection technique more appropriate to higher occupancies, such as mark-sweep-compact, to be used for collection of the old generation.